We study the problem of computing an $\epsilon$-Nash equilibrium in repeatedgames. Earlier work by Borgs et al. [2010] suggests that this problem isintractable. We show that if we make a slight change to their model---modelingthe players as polynomial-time Turing machines that maintain state ---and makesome standard cryptographic hardness assumptions (the existence of public-keyencryption), the problem can actually be solved in polynomial time. Ouralgorithm works not only for games with a finite number of players, but alsofor constant-degree graphical games. As Nash equilibrium is a weak solution concept for extensive form games, weadditionally define and study an appropriate notion of a subgame-perfectequilibrium for computationally bounded players, and show how to efficientlyfind such an equilibrium in repeated games (again, making standardcryptographic hardness assumptions).
展开▼
